/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package com.factory.server.algorithms;

import com.factory.server.dto.EdgeDTO;
import java.util.Arrays;
import java.util.List;

/**
 *
 * @author milos (implemented by pseudocode from algoritmy.net)
 */
public class BellmanFord {  //cesta medzi dvojicou

    public GraphProblemresult execute(List<EdgeDTO> inputEdgeList, int nodesCount, Integer source, Integer target) {
        GraphProblemresult graphProblemresult = new GraphProblemresult();

        double[] distance = new double[nodesCount];
        //double[][] graphDistances = new double[nodesCount][nodesCount];
        int[] predecessors = new int[nodesCount];
        Arrays.fill(distance, Integer.MAX_VALUE);
        distance[source] = 0;
        for (int i = 0; i < nodesCount; i++) {
            for (EdgeDTO edge : inputEdgeList) {
                if (distance[edge.getSource()] + edge.getCost() < distance[edge.getTarget()]) {
                    distance[edge.getTarget()] = distance[edge.getSource()] + edge.getCost();
                    predecessors[edge.getTarget()] = edge.getSource();
                }
                // graphDistances[edge.getSource()][edge.getTarget()] = edge.getCost();
            }
        }

        for (EdgeDTO edge : inputEdgeList) { //kontorla pre zaporny cyklus
            if (distance[edge.getSource()] + edge.getCost() < distance[edge.getTarget()]) {
                graphProblemresult.setNegativeCycle(true);
                return graphProblemresult;
            }
        }

        graphProblemresult.setCost(distance[target]);
        while (true) {
            //graphProblemresult.getShortestPath().add(new EdgeDTO(predecessors[target], target, graphDistances[predecessors[target]][target]));
            graphProblemresult.getShortestPath().add(new EdgeDTO(predecessors[target], target, distance[target] - distance[predecessors[target]]));
            target = predecessors[target];
            if (source == target) {
                break;
            }
        }

        return graphProblemresult;
    }
}
